{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Max Area of Island"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #depth-first-search #breadth-first-search #union-find #array #matrix"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #深度优先搜索 #广度优先搜索 #并查集 #数组 #矩阵"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: maxAreaOfIsland"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #岛屿的最大面积"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个大小为 <code>m x n</code> 的二进制矩阵 <code>grid</code> 。</p>\n",
    "\n",
    "<p><strong>岛屿</strong>&nbsp;是由一些相邻的&nbsp;<code>1</code>&nbsp;(代表土地) 构成的组合，这里的「相邻」要求两个 <code>1</code> 必须在 <strong>水平或者竖直的四个方向上 </strong>相邻。你可以假设&nbsp;<code>grid</code> 的四个边缘都被 <code>0</code>（代表水）包围着。</p>\n",
    "\n",
    "<p>岛屿的面积是岛上值为 <code>1</code> 的单元格的数目。</p>\n",
    "\n",
    "<p>计算并返回 <code>grid</code> 中最大的岛屿面积。如果没有岛屿，则返回面积为 <code>0</code> 。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/05/01/maxarea1-grid.jpg\" style=\"width: 500px; height: 310px;\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>grid = [[0,0,1,0,0,0,0,1,0,0,0,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,0],[0,1,1,0,1,0,0,0,0,0,0,0,0],[0,1,0,0,1,1,0,0,1,0,1,0,0],[0,1,0,0,1,1,0,0,1,1,1,0,0],[0,0,0,0,0,0,0,0,0,0,1,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,0],[0,0,0,0,0,0,0,1,1,0,0,0,0]]\n",
    "<strong>输出：</strong>6\n",
    "<strong>解释：</strong>答案不应该是 <code>11</code> ，因为岛屿只能包含水平或垂直这四个方向上的 <code>1</code> 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>grid = [[0,0,0,0,0,0,0,0]]\n",
    "<strong>输出：</strong>0\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>m == grid.length</code></li>\n",
    "\t<li><code>n == grid[i].length</code></li>\n",
    "\t<li><code>1 &lt;= m, n &lt;= 50</code></li>\n",
    "\t<li><code>grid[i][j]</code> 为 <code>0</code> 或 <code>1</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [max-area-of-island](https://leetcode.cn/problems/max-area-of-island/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [max-area-of-island](https://leetcode.cn/problems/max-area-of-island/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[0,0,1,0,0,0,0,1,0,0,0,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,0],[0,1,1,0,1,0,0,0,0,0,0,0,0],[0,1,0,0,1,1,0,0,1,0,1,0,0],[0,1,0,0,1,1,0,0,1,1,1,0,0],[0,0,0,0,0,0,0,0,0,0,1,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,0],[0,0,0,0,0,0,0,1,1,0,0,0,0]]', '[[0,0,0,0,0,0,0,0]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:\n",
    "        X = len(grid)\n",
    "        Y = len(grid[0]) if X > 0 else 0\n",
    "        dx = [-1, 0, 1, 0]\n",
    "        dy = [0, -1, 0, 1]\n",
    "        def f1(x, y):\n",
    "            result = 0\n",
    "            if grid[x][y] == 1:\n",
    "                grid[x][y] = 0\n",
    "                result += 1\n",
    "                for i in range(4):\n",
    "                    nx = x + dx[i]\n",
    "                    ny = y + dy[i]\n",
    "                    if 0 <= nx and nx < X and 0 <= ny and ny < Y:\n",
    "                        result += f1(nx, ny)\n",
    "            return result\n",
    "        result = 0\n",
    "        for x in range(X):\n",
    "            for y in range(Y):\n",
    "                if grid[x][y] == 1:\n",
    "                    result = max(result, f1(x, y))\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAreaOfIsland(self, grid):\n",
    "        \"\"\"\n",
    "        :type grid: List[List[int]]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        a=[]\n",
    "        b=[]\n",
    "        \n",
    "        for i in range(len(grid)):\n",
    "            for j in range(len(grid[0])):\n",
    "                if grid[i][j]==1:\n",
    "                    a=[]\n",
    "                    a.append([i,j])\n",
    "                    grid[i][j]=-1\n",
    "                    d=1\n",
    "                    while True:\n",
    "                        c=[]\n",
    "                        for k in a:\n",
    "                            for m,n in [[-1,0],[1,0],[0,-1],[0,1]]:\n",
    "                                if k[0]+m>-1 and k[1]+n>-1:\n",
    "                                    try:\n",
    "                                        if grid[k[0]+m][k[1]+n]==1:\n",
    "                                            grid[k[0]+m][k[1]+n]=-1\n",
    "                                            d+=1\n",
    "                                            c.append([k[0]+m,k[1]+n])\n",
    "                                    except IndexError:\n",
    "                                        pass\n",
    "                        if len(c)==0:\n",
    "                            break\n",
    "                        a=c\n",
    "                    b.append(d)\n",
    "                    \n",
    "        if len(b)==0:\n",
    "            return 0\n",
    "        if len(b)==1:\n",
    "            return b[0]\n",
    "        return max(b)\n",
    "                        \n",
    "                        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    class UnionFindSet(object):\n",
    "        def __init__(self, data_list):\n",
    "            \"\"\"初始化两个字典，一个保存节点的父节点，另外一个保存父节点的大小\n",
    "            初始化的时候，将节点的父节点设为自身，size设为1\"\"\"\n",
    "            self.father_dict = {}\n",
    "            self.size_dict = {}\n",
    "\n",
    "            for node in data_list:\n",
    "                self.father_dict[node] = node\n",
    "                self.size_dict[node] = 1\n",
    "\n",
    "        def find_head(self, node):\n",
    "            \"\"\"使用递归的方式来查找父节点\n",
    "\n",
    "            在查找父节点的时候，顺便把当前节点移动到父节点上面\n",
    "            这个操作算是一个优化\n",
    "            \"\"\"\n",
    "            father = self.father_dict[node]\n",
    "            if(node != father):\n",
    "                father = self.find_head(father)\n",
    "            self.father_dict[node] = father\n",
    "            return father\n",
    "\n",
    "        def is_same_set(self, node_a, node_b):\n",
    "            \"\"\"查看两个节点是不是在一个集合里面\"\"\"\n",
    "            return self.find_head(node_a) == self.find_head(node_b)\n",
    "\n",
    "        def union(self, node_a, node_b):\n",
    "            \"\"\"将两个集合合并在一起\"\"\"\n",
    "            #print ('unioned')\n",
    "            if node_a is None or node_b is None:\n",
    "                return\n",
    "\n",
    "            a_head = self.find_head(node_a)\n",
    "            b_head = self.find_head(node_b)\n",
    "\n",
    "            if(a_head != b_head):\n",
    "                a_set_size = self.size_dict[a_head]\n",
    "                b_set_size = self.size_dict[b_head]\n",
    "                if(a_set_size >= b_set_size):\n",
    "                    self.father_dict[b_head] = a_head\n",
    "                    self.size_dict[a_head] = a_set_size + b_set_size\n",
    "                else:\n",
    "                    self.father_dict[a_head] = b_head\n",
    "                    self.size_dict[b_head] = a_set_size + b_set_size\n",
    "        def MaxNodeSize(self):\n",
    "            return max(list(self.size_dict.values()))\n",
    "    \n",
    "    def get_address(self,i,j,grid):\n",
    "        return i*len(grid[0])+j+1\n",
    "    def get_index(self,address,grid):\n",
    "        if address%len(grid[0])!=0:\n",
    "            return [int(address/len(grid[0])),(address%len(grid[0]))-1]\n",
    "        else:\n",
    "            return [int(address/len(grid[0]))-1,len(grid[0])-1]\n",
    "    def maxAreaOfIsland(self, grid):\n",
    "        dirts=[]\n",
    "        for i in range(len(grid)):\n",
    "            for j in range(len(grid[0])):\n",
    "                if grid[i][j]==1:\n",
    "                    dirts.append(self.get_address(i,j,grid))\n",
    "        if dirts==[]:\n",
    "            return 0\n",
    "        Union=self.UnionFindSet(dirts)\n",
    "        for dirt in dirts:\n",
    "            i = self.get_index(dirt,grid)[0]\n",
    "            j=self.get_index(dirt,grid)[1]\n",
    "            if i!=len(grid)-1 and self.get_address(i+1,j,grid) in dirts: \n",
    "                if not Union.is_same_set(self.get_address(i,j,grid),self.get_address(i+1,j,grid)):\n",
    "                    Union.union(self.get_address(i,j,grid),self.get_address(i+1,j,grid))\n",
    "            if i!=0 and self.get_address(i-1,j,grid) in dirts: \n",
    "                if not Union.is_same_set(self.get_address(i,j,grid),self.get_address(i-1,j,grid)):\n",
    "                    Union.union(self.get_address(i,j,grid),self.get_address(i-1,j,grid))\n",
    "            if j!=len(grid[0])-1 and self.get_address(i,j+1,grid) in dirts: \n",
    "                if not Union.is_same_set(self.get_address(i,j,grid),self.get_address(i,j+1,grid)):\n",
    "                    Union.union(self.get_address(i,j,grid),self.get_address(i,j+1,grid))\n",
    "            if j!=0 and self.get_address(i,j-1,grid) in dirts: \n",
    "                if not Union.is_same_set(self.get_address(i,j,grid),self.get_address(i,j-1,grid)):\n",
    "                    Union.union(self.get_address(i,j,grid),self.get_address(i,j-1,grid))\n",
    "            #print(dirt)\n",
    "            #print([i,j])\n",
    "            #print(list(Union.father_dict.values()))\n",
    "        \n",
    "        return Union.MaxNodeSize()\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAreaOfIsland(self, grid):\n",
    "        \"\"\"\n",
    "        :type grid: List[List[int]]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        maxArea = 0\n",
    "        row = len(grid)\n",
    "        column = len(grid[0])\n",
    "        totalPoints = [[0 for i in range(column)] for i in range(row)]\n",
    "        for i in range(0, row):\n",
    "            for j in range(0, column):\n",
    "                if grid[i][j] == 0:\n",
    "                    continue\n",
    "                else:\n",
    "                    if totalPoints[i][j]:\n",
    "                        continue\n",
    "                    totalPoints[i][j] = 1\n",
    "                    points = [[i, j]]\n",
    "                    newArea = []\n",
    "                    oldNum = 0\n",
    "                    while True:\n",
    "                        currNum = len(points)\n",
    "                        for p in range(oldNum, currNum):\n",
    "                            point = points[p]\n",
    "                            x = point[0]\n",
    "                            y = point[1]\n",
    "                            if x >= 1 and grid[x - 1][y] == 1 and totalPoints[x - 1][y] == 0:\n",
    "                                newArea.append([x - 1, y])\n",
    "                                totalPoints[x-1][y] = 1\n",
    "                            if y >= 1 and grid[x][y - 1] == 1 and totalPoints[x][y - 1] == 0:\n",
    "                                newArea.append([x, y - 1])\n",
    "                                totalPoints[x][y-1] =1\n",
    "                            if x < row - 1 and grid[x + 1][y] == 1 and totalPoints[x + 1][y] == 0:\n",
    "                                newArea.append([x + 1, y])\n",
    "                                totalPoints[x+1][y] = 1\n",
    "                            if y < column - 1 and grid[x][y + 1] == 1 and totalPoints[x][y + 1] == 0:\n",
    "                                newArea.append([x, y + 1])\n",
    "                                totalPoints[x][y+1] = 1\n",
    "                        if len(newArea) == 0:\n",
    "                            break\n",
    "                        else:\n",
    "                            oldNum = len(points)\n",
    "                            points = points + newArea\n",
    "                            newArea.clear()\n",
    "\n",
    "                    if len(points) > maxArea:\n",
    "                        maxArea = len(points)\n",
    "\n",
    "\n",
    "        return maxArea\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAreaOfIsland(self, grid):\n",
    "        \"\"\"\n",
    "        :type grid: List[List[int]]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        tmp = []\n",
    "        for i in range(len(grid)):\n",
    "            tmp.append([])\n",
    "            for j in range(len(grid[0])):\n",
    "                tmp[i].append(False)\n",
    "        max_area = 0\n",
    "        for i in range(len(grid)):\n",
    "            for j in range(len(grid[0])):\n",
    "                if tmp[i][j]:\n",
    "                    continue\n",
    "                if grid[i][j] == 0:\n",
    "                    tmp[i][j] = True\n",
    "                    continue\n",
    "                stack = [[i, j]]\n",
    "                current_area = 0\n",
    "                while stack:\n",
    "                    row, column = stack.pop()\n",
    "                    if row < 0 or column < 0 or row >= len(grid) or column >= len(grid[0]):\n",
    "                        continue\n",
    "                    if tmp[row][column]:\n",
    "                        continue\n",
    "                    tmp[row][column] = True\n",
    "                    if grid[row][column] == 0:\n",
    "                        continue\n",
    "                    current_area += 1\n",
    "                    stack.append([row + 1, column])\n",
    "                    stack.append([row - 1, column])\n",
    "                    stack.append([row, column + 1])\n",
    "                    stack.append([row, column - 1])\n",
    "                max_area = max(max_area, current_area)\n",
    "        return max_area"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAreaOfIsland(self, grid):\n",
    "        \"\"\"\n",
    "        :type grid: List[List[int]]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        maxnum=0\n",
    "        h=len(grid)\n",
    "        for i in range(h):\n",
    "            m=len(grid[i])\n",
    "            for j in range(m):\n",
    "                if grid[i][j]==1:\n",
    "                    num=0\n",
    "                    a=[(i,j)]\n",
    "                    grid[i][j]=0\n",
    "                    while len(a)>0:\n",
    "                        num+=1\n",
    "                        # print(num,a[-1],a)\n",
    "                        ti,tj=a[-1][0],a[-1][1]\n",
    "                        a.pop()\n",
    "                        # 查找这个位置有没有连起来\n",
    "                        if ti>0 and grid[ti-1][tj]==1:#left\n",
    "                            grid[ti-1][tj]=0\n",
    "                            a.append((ti-1,tj))\n",
    "                        if ti<h-1 and grid[ti+1][tj]==1:#right\n",
    "                            grid[ti+1][tj]=0\n",
    "                            a.append((ti+1,tj))\n",
    "                        if tj>0 and grid[ti][tj-1]==1:#up\n",
    "                            grid[ti][tj-1]=0\n",
    "                            a.append((ti,tj-1))\n",
    "                        if tj<m-1 and grid[ti][tj+1]==1:#down\n",
    "                            grid[ti][tj+1]=0\n",
    "                            a.append((ti,tj+1))    \n",
    "                    if num>maxnum:maxnum=num\n",
    "        return maxnum"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAreaOfIsland(self, grid):\n",
    "        \"\"\"\n",
    "        :type grid: List[List[int]]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        \n",
    "        ans = 0\n",
    "        for i in range(len(grid)):\n",
    "            for j in range(len(grid[0])):\n",
    "                if(grid[i][j]!=-1):\n",
    "                    if grid[i][j]==1:\n",
    "                        ans = max(self.dfs(i,j,grid),ans)\n",
    "                    else:\n",
    "                        grid[i][j]==-1\n",
    "        return ans\n",
    "                         \n",
    "    def dfs(self,r,c,grid):\n",
    "        cnt = 1\n",
    "        direction = [[1,0],[0,1],[-1,0],[0,-1]]\n",
    "        q = collections.deque()\n",
    "        grid[r][c] = -1\n",
    "        q.append((r,c))\n",
    "        while(q):\n",
    "            curr = q.popleft()\n",
    "            for i in range(4):\n",
    "                tmp = (curr[0]+direction[i][0],curr[1]+direction[i][1])\n",
    "                if 0<=tmp[0]<len(grid) and 0<=tmp[1]<len(grid[0]) and grid[tmp[0]][tmp[1]]==1:\n",
    "                    grid[tmp[0]][tmp[1]] = -1\n",
    "                    q.append(tmp)\n",
    "                    cnt+=1\n",
    "        return cnt\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAreaOfIsland(self, grid):\n",
    "        \"\"\"\n",
    "        :type grid: List[List[int]]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        rows=len(grid)\n",
    "        if rows==0:\n",
    "            return 0\n",
    "        cols=len(grid[0])\n",
    "        if cols==0:\n",
    "            return 0\n",
    "        max_area=0\n",
    "        for idx in range(rows):\n",
    "            for idy in range(cols):\n",
    "                if grid[idx][idy]==0:\n",
    "                    continue\n",
    "                area=0\n",
    "                stack=[(idx,idy)]\n",
    "                while len(stack)>0:\n",
    "                    x,y=stack.pop()\n",
    "                    if 0<=x<rows and 0<=y<cols and grid[x][y]==1:\n",
    "                        grid[x][y]=0\n",
    "                        area+=1\n",
    "                        stack.extend([(x-1,y),(x+1,y),(x,y-1),(x,y+1)])\n",
    "                max_area=max(area,max_area)\n",
    "        return max_area\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAreaOfIsland(self, grid):\n",
    "        \"\"\"\n",
    "        :type grid: List[List[int]]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        res = 0\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                res = max(res, self.dfs(i, j, m, n, grid))\n",
    "        return res\n",
    "\n",
    "    def dfs(self, i, j, m, n, grid):\n",
    "        if i < 0 or i >=m or j < 0 or j >= n:\n",
    "            return 0\n",
    "        if grid[i][j] == 1:\n",
    "            grid[i][j] = 2\n",
    "            res = 1\n",
    "            res += self.dfs(i+1, j, m, n,grid)\n",
    "            res += self.dfs(i-1, j, m, n, grid)\n",
    "            res += self.dfs(i, j+1, m, n, grid)\n",
    "            res += self.dfs(i, j-1, m, n, grid)\n",
    "            return res\n",
    "        else:\n",
    "            return 0\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAreaOfIsland(self, grid):\n",
    "        \"\"\"\n",
    "        :type grid: List[List[int]]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        maximum = 0\n",
    "        for i in range(0,len(grid)):\n",
    "            for j in range(0,len(grid[0])):\n",
    "                if grid[i][j] == 1:\n",
    "                    temp = self.countArea(grid, i, j)\n",
    "                    if temp > maximum:\n",
    "                        maximum = temp\n",
    "        return maximum\n",
    "    \n",
    "    def countArea(self, grid, i, j):\n",
    "        grid[i][j] = 0\n",
    "        res = 1\n",
    "        if i-1 >= 0 and grid[i-1][j] == 1:\n",
    "            res += self.countArea(grid, i-1, j)\n",
    "        if i+1 < len(grid) and grid[i+1][j] == 1:\n",
    "            res += self.countArea(grid, i+1, j)\n",
    "        if j-1 >= 0 and grid[i][j-1] == 1:\n",
    "            res += self.countArea(grid, i, j-1)\n",
    "        if j+1 < len(grid[0]) and grid[i][j+1] == 1:\n",
    "            res += self.countArea(grid, i ,j+1)\n",
    "        \n",
    "        return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAreaOfIsland(self, grid):\n",
    "        \"\"\"\n",
    "        :type grid: List[List[int]]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        if len(grid) == 0:\n",
    "            return 0\n",
    "        \n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "        \n",
    "        max_Area = 0\n",
    "        \n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 1:\n",
    "                    max_Area = max(max_Area, self.dfs(grid, i, j))\n",
    "        return max_Area\n",
    "    \n",
    "    def dfs(self, grid, i, j):\n",
    "        if i<0 or i>=len(grid) or j<0 or j>=len(grid[0]) or grid[i][j] == 0:\n",
    "            return 0\n",
    "        grid[i][j] = 0\n",
    "        res = 1 + self.dfs(grid, i-1, j) + self.dfs(grid, i+1, j) + self.dfs(grid, i, j-1) + self.dfs(grid, i, j+1)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAreaOfIsland(self, grid: 'List[List[int]]') -> 'int':\n",
    "        if not grid:\n",
    "            return 0\n",
    "        dires = [[1,0], [0,1], [-1,0], [0,-1]]\n",
    "        ans = [0]\n",
    "        tmp = (len(grid), len(grid[0]))\n",
    "        step = [0]\n",
    "        def dfs(row, col):\n",
    "            if row >= tmp[0] or col >= tmp[1] or row < 0 or col < 0:\n",
    "                ans[0] = max(step[0], ans[0])\n",
    "                return\n",
    "            if grid[row][col] == 0 or grid[row][col] == -1:\n",
    "                ans[0] = max(step[0], ans[0])\n",
    "                return \n",
    "            \n",
    "            grid[row][col] = -1\n",
    "            step[0] += 1\n",
    "            for dire in dires:\n",
    "                nextr = row + dire[0]\n",
    "                nextc = col + dire[1]\n",
    "                dfs(nextr, nextc)\n",
    "                \n",
    "        for row in range(tmp[0]):\n",
    "            for col in range(tmp[1]):\n",
    "                if grid[row][col] not in {0, -1}:\n",
    "                    dfs(row, col)\n",
    "                    #print(grid)\n",
    "                    step[0] = 0\n",
    "        return ans[0]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def maxAreaOfIsland(self, grid):\n",
    "        \"\"\"\n",
    "        :type grid: List[List[int]]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        def find(i,j):\n",
    "            if i<0 or i>=r or j <0 or j>=c:return 0\n",
    "            \n",
    "            if grid[i][j]:\n",
    "                grid[i][j]=0\n",
    "                \n",
    "                return 1+find(i-1,j)+find(i+1,j)+find(i,j-1)+find(i,j+1)\n",
    "                 \n",
    "            else:return 0\n",
    "                \n",
    "                \n",
    "        res=[]\n",
    "        r,c=len(grid),len(grid[0])\n",
    "        \n",
    "        for i in range(r):\n",
    "            for j in range(c):\n",
    "                res.append(find(i,j))\n",
    "        return max(res) if res else 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAreaOfIsland(self, grid):\n",
    "        \"\"\"\n",
    "        :type grid: List[List[int]]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        if not grid or not grid[0]:\n",
    "            return 0\n",
    "\n",
    "        m, n = len(grid), len(grid[0])      \n",
    "        visited = [[0] * n for i in range(m)]\n",
    "        directions = ((1, 0), (-1, 0), (0, 1), (0, -1))\n",
    "\n",
    "        def dfs(pos):\n",
    "            i, j = pos\n",
    "            if not visited[i][j]:\n",
    "                visited[i][j] = 1\n",
    "                length[0] += 1\n",
    "                for x, y in directions:\n",
    "                    ii, jj = i + x, j + y\n",
    "                    if 0 <= ii < m and 0 <= jj < n:\n",
    "                        if grid[ii][jj] == grid[i][j]:\n",
    "                            dfs((ii, jj))\n",
    "\n",
    "        record = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if not visited[i][j] and grid[i][j] == 1:\n",
    "                    length = [0]\n",
    "                    dfs((i, j))\n",
    "                    record = max(record, length[0])\n",
    "\n",
    "        return record"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAreaOfIsland(self, grid):\n",
    "        \"\"\"\n",
    "        :type grid: List[List[int]]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        def cal(L,i,j):\n",
    "            c = 1\n",
    "            x = len(L)\n",
    "            y = len(L[0])\n",
    "            L[i][j] = 0\n",
    "            if i-1>=0 and L[i-1][j]: #上\n",
    "                c = c + cal(L,i-1,j)\n",
    "            if j+1 < y and L[i][j+1]: #右\n",
    "                c = c + cal(L,i,j+1)\n",
    "            if  i+1 < x and L[i+1][j]: #下\n",
    "                c = c + cal(L,i+1,j)\n",
    "            if j-1>=0 and L[i][j-1]: #左\n",
    "                c = c + cal(L,i,j-1)\n",
    "            return c\n",
    "\n",
    "\n",
    "        lenr = len(grid)\n",
    "        lenc = len(grid[0])\n",
    "        count = 0\n",
    "        result = 0\n",
    "        for i in range(lenr):\n",
    "            for j in range(lenc):\n",
    "                if grid[i][j] == 1:\n",
    "                    count = cal(grid,i,j)\n",
    "                    result = max(result,count)\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAreaOfIsland(self, grid):\n",
    "        \"\"\"\n",
    "        :type grid: List[List[int]]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        max_area = 0\n",
    "        if len(grid) == 0:\n",
    "            return max_area\n",
    "        for i in range(len(grid)):\n",
    "            for j in range(len(grid[0])):\n",
    "                if grid[i][j] == 1:\n",
    "                    max_area = max(max_area, self.dfs(i, j, grid))\n",
    "        return max_area\n",
    "    \n",
    "    def dfs(self, i, j, grid):\n",
    "        area = 0\n",
    "        if i < 0 or j < 0 or i >= len(grid) or j >= len(grid[0]):\n",
    "            return area\n",
    "        if grid[i][j] == 1:\n",
    "            area += 1\n",
    "            grid[i][j] = 0\n",
    "            direction = [[-1, 0], [1, 0], [0, -1], [0, 1]]\n",
    "            for d in direction:\n",
    "                area += self.dfs(i + d[0], j + d[1], grid)\n",
    "        return area"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:\n",
    "        if len(grid)==0 or len(grid[0])==0:\n",
    "            return 0\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "        maxarea=0\n",
    "        \n",
    "        def dfs(grid, i, j, m, n):\n",
    "            if i<0 or i>=m or j<0 or j>=n or grid[i][j]==0:\n",
    "                return 0\n",
    "            grid[i][j]=0\n",
    "            return 1+dfs(grid, i+1, j, m, n)+dfs(grid, i-1, j, m, n)+dfs(grid, i, j+1, m, n)+dfs(grid, i, j-1, m, n)\n",
    "        \n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j]==1:\n",
    "                    maxarea = max(dfs(grid, i, j, m, n), maxarea)\n",
    "        return maxarea"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAreaOfIsland(self, grid):\n",
    "        f = dict()\n",
    "        _max = 0\n",
    "        for floor in grid:\n",
    "            s = dict()\n",
    "            for i in range(len(floor)):\n",
    "                if floor[i] == 1:\n",
    "                    # 有水平连接\n",
    "                    head = self.get_head(i, s)\n",
    "                    if head == i:\n",
    "                        s[i] = 1\n",
    "                    else:\n",
    "                        s[head] += 1\n",
    "                        s[i] = str(head)\n",
    "\n",
    "                    f_head = self.get_head(i+1, f)\n",
    "                    # 垂直相连时\n",
    "                    if f_head != i+1:\n",
    "                        # 水平父节点\n",
    "                        tem = i\n",
    "                        if type(s[i]) == str:\n",
    "                            tem = int(s[i])\n",
    "\n",
    "                        fn = f[f_head]\n",
    "                        # 上层岛屿已和这层岛屿连接\n",
    "                        if type(fn) == tuple:\n",
    "                            # 上层岛屿和这层岛屿连接的头点\n",
    "                            head = fn[0]\n",
    "                            # 判断水平父岛屿和垂直父岛屿是否是同一个，是同一个则不用加\n",
    "                            if head != tem:\n",
    "                                s[head] += s[tem]\n",
    "                                s[tem] = str(head)\n",
    "                            # tem = fn[0]\n",
    "                            # s[i] = str(tem)\n",
    "                            # if flag:s\n",
    "                            #     fn = 0\n",
    "                            # else:\n",
    "                            #     fn = 0 if i-1 >= 0 and floor[i-1] == 1 else 1\n",
    "                        # 未和这层连接\n",
    "                        else:\n",
    "                            f[f_head] = (tem, )\n",
    "                            s[tem] += fn\n",
    "\n",
    "            for v in f.values():\n",
    "                if type(v) == int and v > _max:\n",
    "                    _max = v\n",
    "            f = s\n",
    "\n",
    "        # 最后来一次\n",
    "        for v in f.values():\n",
    "            if type(v) == int and v > _max:\n",
    "                _max = v\n",
    "        return _max\n",
    "\n",
    "    def get_head(self, i, s):\n",
    "        if type(s.get(i-1)) == int:\n",
    "            return i-1\n",
    "        elif type(s.get(i-1)) == str:\n",
    "            return self.get_head(int(s[i-1])+1, s)\n",
    "        elif type(s.get(i-1)) == tuple:\n",
    "            return i-1\n",
    "        else:\n",
    "            return i\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:\n",
    "        if not grid:\n",
    "            return 0\n",
    "        m=len(grid)\n",
    "        n=len(grid[0])\n",
    "        visited=[[False]*n for _ in range(0,m)]\n",
    "        #print(visited)\n",
    "        level=0\n",
    "        res=[]\n",
    "        for i in range(0,m):\n",
    "            for j in range(0,n):\n",
    "                if grid[i][j]==1 and  visited[i][j]==False:\n",
    "                    queue=[(i,j)]\n",
    "                    visited[i][j]=True\n",
    "                    #print(i,j)\n",
    "                    res.append([])\n",
    "                    #print(res)\n",
    "                    while queue:\n",
    "                        x,y=queue.pop(0)\n",
    "                        res[level].append((x,y))\n",
    "                        for dx,dy in [[0,1],[0,-1],[-1,0],[1,0]]:\n",
    "                            newX=x+dx\n",
    "                            newY=y+dy\n",
    "                            if newX>=0 and newX<m and newY>=0 and newY<n and grid[newX][newY]==1 and visited[newX][newY]==False:\n",
    "                                visited[newX][newY]=True\n",
    "                                queue.append((newX,newY))\n",
    "                    level=level+1\n",
    "        print(res)\n",
    "        maxL=0\n",
    "        for l in res:\n",
    "            maxL=max(len(l),maxL)\n",
    "        return maxL\n",
    "                \n",
    "                        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:\n",
    "        if not grid:\n",
    "            return 0\n",
    "\n",
    "        total0 = 0\n",
    "        total1 = 0\n",
    "        r = len(grid)\n",
    "        c = len(grid[0])\n",
    "        for i in range(len(grid)):\n",
    "            total0 += grid[i].count(0)\n",
    "        if total0 == r*c: \n",
    "            return 0\n",
    "        \n",
    "        visited = [[False for i in range(c)] for j in range(r)]\n",
    "        queue = []\n",
    "        ans = 0\n",
    "\n",
    "        for i in range(r):\n",
    "            for j in range(c):\n",
    "                if grid[i][j] == 1 and not visited[i][j]: #if it is a island and not visit yet\n",
    "                    temp = 1\n",
    "                    visited[i][j] = True\n",
    "                    queue.append([i,j])\n",
    "                    while queue:\n",
    "                        x,y = queue.pop(0)\n",
    "                        for row,col in [[x-1,y],[x+1,y],[x,y-1],[x,y+1]]:\n",
    "                            if 0<=row<r and 0<=col<c and not visited[row][col]:\n",
    "                                if grid[row][col] == 1:\n",
    "                                    temp += 1\n",
    "                                    queue.append([row,col])\n",
    "                                    visited[row][col] = True\n",
    "\n",
    "                    ans = max(ans,temp)\n",
    "                    temp = 0\n",
    "\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:\n",
    "        l = []\n",
    "        res = 0\n",
    "        for i in range(len(grid)):\n",
    "            for j in range(len(grid[0])):\n",
    "                if grid[i][j] == 0:\n",
    "                    continue\n",
    "                else:\n",
    "                    l.append([i,j])\n",
    "                    grid[i][j] = 0\n",
    "                    dao = 0\n",
    "                    while l:\n",
    "                        dao +=1\n",
    "                        res = max(res,dao)\n",
    "\n",
    "                        #print(l,dao)\n",
    "\n",
    "                        i,j = l.pop(0)\n",
    "                        for x,y in [[-1,0],[0,-1],[1,0],[0,1]]:\n",
    "                            xx = x+i\n",
    "                            yy = y+j\n",
    "                            if 0 <= xx <len(grid) and 0 <= yy < len(grid[0]) and grid[xx][yy]>0:\n",
    "                                l.append([xx,yy])\n",
    "                                grid[xx][yy] = 0\n",
    "\n",
    "\n",
    "                        \n",
    "\n",
    "        return res\n",
    "        \n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:\n",
    "        if not grid or len(grid[0])<1:\n",
    "            return 0\n",
    "        \n",
    "        rows, cols = len(grid), len(grid[0])\n",
    "        max_area = 0\n",
    "        for i in range(rows):\n",
    "            for j in range(cols):\n",
    "                if grid[i][j] == 1:\n",
    "                    max_area = max(max_area, self.bfs(grid, i, j, rows, cols))\n",
    "        return max_area\n",
    "    \n",
    "    def bfs(self, grid, x, y, rows, cols):\n",
    "        steps = [[0, 1], [1, 0], [0, -1], [-1, 0]]\n",
    "        queue = [(x, y)]\n",
    "        area = 1\n",
    "        grid[x][y] = 0\n",
    "        while queue:\n",
    "            x, y = queue.pop(0)\n",
    "            for step in steps:\n",
    "                x_, y_ = x+step[0], y+step[1]\n",
    "                if 0<=x_<rows and 0<=y_<cols and grid[x_][y_]==1:\n",
    "                    area += 1\n",
    "                    queue.append((x_, y_))\n",
    "                    grid[x_][y_] = 0\n",
    "        return area"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:\n",
    "        dx=[-1,0,0,1]\n",
    "        dy=[0,1,-1,0]\n",
    "        maxs=0\n",
    "        for i in range(len(grid)):\n",
    "            for j in range(len(grid[0])):\n",
    "                s=0\n",
    "                if grid[i][j]==1:\n",
    "                    grid[i][j]=0\n",
    "                    s+=1\n",
    "                    #island=[]\n",
    "                    #island.append([i,j])\n",
    "                    island=collections.deque()\n",
    "                    island.append([i,j])\n",
    "                    while len(island)>0:\n",
    "                        #x,y=island[0]\n",
    "                        #del island[0]\n",
    "                        x,y=island.popleft()\n",
    "                        for k in range(4):\n",
    "                            nx=x+dx[k]\n",
    "                            ny=y+dy[k]\n",
    "                            if 0<=nx<len(grid) and 0<=ny<len(grid[0]) and grid[nx][ny]==1 :\n",
    "                                grid[nx][ny]=0\n",
    "                                s+=1\n",
    "                                island.append([nx,ny])\n",
    "                    maxs=max(s,maxs)\n",
    "        return maxs"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAreaOfIsland(self, grid) -> int:\n",
    "        if not grid or not grid[0]:\n",
    "            return 0\n",
    "\n",
    "        # 这一段是套路\n",
    "        rows, cols = len(grid), len(grid[0])  # rows cols\n",
    "        marked = [[False for i in range(cols)] for j in range(rows)]  # 是否走过\n",
    "        directions = [[-1, 0], [0, 1], [1, 0], [0, -1]]  # 上右下左\n",
    "        queue = []\n",
    "\n",
    "        max_area = 0\n",
    "        for i in range(rows):\n",
    "            for j in range(cols):\n",
    "                if marked[i][j] is False and grid[i][j] == 1:\n",
    "                    queue.append([i, j])  # 入队\n",
    "                    marked[i][j] = True   # 标记\n",
    "                    current_area = 0\n",
    "                    while queue:\n",
    "                        current = queue.pop(0)\n",
    "                        current_area += 1\n",
    "                        for direction in directions:\n",
    "                            next_x = current[0] + direction[0]\n",
    "                            next_y = current[1] + direction[1]\n",
    "                            if 0 <= next_x < rows and 0 <= next_y < cols and marked[next_x][next_y] is False and grid[next_x][next_y] == 1:\n",
    "                                queue.append([next_x, next_y])\n",
    "                                marked[next_x][next_y] = True\n",
    "                    max_area = max(max_area, current_area)\n",
    "        \n",
    "        return max_area"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:\n",
    "        if not grid: return 0\n",
    "        rownum = len(grid)\n",
    "        colnum = len(grid[0])\n",
    "        land = []\n",
    "        for i in range(rownum):\n",
    "            for j in range(colnum):\n",
    "                if grid[i][j]==1:\n",
    "                    land.append((i,j))\n",
    "        if not land: return 0\n",
    "        maxarea = 0\n",
    "        x = [1,0,0,-1]\n",
    "        y = [0,1,-1,0]\n",
    "        for a in land:\n",
    "            if grid[a[0]][a[1]]==0:\n",
    "                continue\n",
    "            stack = [a]\n",
    "            grid[a[0]][a[1]]=0\n",
    "            area = 1\n",
    "            while stack:\n",
    "                cur = stack.pop()\n",
    "                for b in range(4):\n",
    "                    if 0<=cur[0]+x[b]<rownum and 0<=cur[1]+y[b]<colnum and grid[cur[0]+x[b]][cur[1]+y[b]]==1:\n",
    "                        stack.append((cur[0]+x[b],cur[1]+y[b]))\n",
    "                        area += 1\n",
    "                        grid[cur[0]+x[b]][cur[1]+y[b]]=0\n",
    "            maxarea = max(maxarea,area)\n",
    "        return maxarea\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import queue\n",
    "\n",
    "class Solution:\n",
    "    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:\n",
    "        leni = len(grid)\n",
    "        if leni == 0:\n",
    "            return 0\n",
    "        lenj = len(grid[0])\n",
    "        result = 0\n",
    "        #check = [[0] * lenj for _ in range(leni)]\n",
    "        for i in range(leni):\n",
    "            if sum(grid[i]) > 0:\n",
    "                for j in range(lenj):\n",
    "                    print(i)\n",
    "                    print(j)\n",
    "                    if grid[i][j] == 1:\n",
    "                        tqueue = queue.Queue()\n",
    "                        grid[i][j] = 0\n",
    "                        tqueue.put([i, j])\n",
    "                        tmp_s = 0\n",
    "                        while not tqueue.empty():\n",
    "                            f, s = tqueue.get()\n",
    "                            tmp_s += 1\n",
    "                            for x, y in [[f+1, s], [f-1, s], [f, s-1], [f, s+1]]:\n",
    "                                if 0 <= x < leni and 0 <= y < lenj:\n",
    "                                    if grid[x][y] == 1:\n",
    "                                        grid[x][y] = 0\n",
    "                                        tqueue.put([x, y])\n",
    "                        result = max(tmp_s, result)\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:\n",
    "        row=len(grid)\n",
    "        if not row:\n",
    "            return 0\n",
    "        col=len(grid[0])\n",
    "        if not col:\n",
    "            return 0\n",
    "        maxcnt=0\n",
    "        queue=[]\n",
    "        for i in range(row):\n",
    "            for j in range(col):\n",
    "                if grid[i][j]==1:\n",
    "                    cnt=0\n",
    "                    queue.append((i,j))\n",
    "                    cnt+=1\n",
    "                    while queue:\n",
    "                        cur_i,cur_j=queue.pop(0)\n",
    "                        grid[cur_i][cur_j]=0\n",
    "                        for x,y in [(1,0),(-1,0),(0,1),(0,-1)]:\n",
    "                            tmp_i,tmp_j=cur_i+x,cur_j+y\n",
    "                            if 0<=tmp_i<row and 0<=tmp_j<col and grid[tmp_i][tmp_j]==1 and (tmp_i,tmp_j)not in queue:\n",
    "                                queue.append((tmp_i,tmp_j))\n",
    "                                cnt+=1\n",
    "                    maxcnt=max(maxcnt,cnt)\n",
    "        return maxcnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:\n",
    "\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        maxArea = 0\n",
    "        for r in range(m):\n",
    "            for c in range(n):\n",
    "                stack = deque()\n",
    "                stack.append((r, c))\n",
    "                area = 0\n",
    "\n",
    "                while stack:\n",
    "                    r_, c_ = stack.popleft()\n",
    "\n",
    "                    if r_ >= 0 and r_ < m and c_ >= 0 and c_ < n and grid[r_][c_] == 1:\n",
    "                        area += 1\n",
    "                        grid[r_][c_] = 2\n",
    "\n",
    "                        stack.append((r_ + 1, c_))\n",
    "                        stack.append((r_ - 1, c_))\n",
    "                        stack.append((r_, c_ + 1))\n",
    "                        stack.append((r_, c_ - 1))\n",
    "\n",
    "                if maxArea < area:\n",
    "                    maxArea = area\n",
    "        \n",
    "        return maxArea"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:\n",
    "        def bfs(i,j):\n",
    "            queue = [(i,j)]\n",
    "            grid[i][j] = 0\n",
    "            area = 1\n",
    "            while queue:\n",
    "                x,y = queue.pop(0)\n",
    "                for new_x,new_y in [(x + 1,y),(x - 1,y),(x,y + 1),(x,y - 1)]:\n",
    "                    if 0 <= new_x < n and 0 <= new_y < m and grid[new_x][new_y] == 1:\n",
    "                        grid[new_x][new_y] = 0\n",
    "                        area += 1\n",
    "                        queue.append((new_x,new_y))\n",
    "            return area\n",
    "\n",
    "        n,m = len(grid),len(grid[0])\n",
    "        res = 0\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                if grid[i][j] == 1:\n",
    "                    res = max(res,bfs(i,j))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:\n",
    "        ans = 0\n",
    "        for i, l in enumerate(grid):\n",
    "            for j, n in enumerate(l):\n",
    "                cur = 0\n",
    "                q = collections.deque([(i, j)])\n",
    "                while q:\n",
    "                    cur_i, cur_j = q.popleft()\n",
    "                    if cur_i < 0 or cur_j < 0 or cur_i == len(grid) or cur_j == len(grid[0]) or grid[cur_i][cur_j] != 1:\n",
    "                        continue\n",
    "                    cur += 1\n",
    "                    grid[cur_i][cur_j] = 0\n",
    "                    for di, dj in [[0, 1], [0, -1], [1, 0], [-1, 0]]:\n",
    "                        next_i, next_j = cur_i + di, cur_j + dj\n",
    "                        q.append((next_i, next_j))\n",
    "                ans = max(ans, cur)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:\n",
    "\n",
    "        H, W = len(grid), len(grid[0])\n",
    "\n",
    "        def get_area(i, j):\n",
    "            area = 0\n",
    "            queue = []\n",
    "            visited = set()\n",
    "\n",
    "            queue.append((i, j))\n",
    "            visited.add((i, j))\n",
    "            # grid[i][j] = 2\n",
    "            # area += 1\n",
    "            \n",
    "            while queue:\n",
    "                a, b = queue.pop(0)\n",
    "                grid[a][b] = 2\n",
    "                area += 1\n",
    "                for (a, b) in ((a+1, b), (a-1, b), (a, b+1), (a, b-1)):\n",
    "                    if not ((0<=a<=H-1) and (0<=b<=W-1)):\n",
    "                        continue\n",
    "                    if not grid[a][b] == 1:\n",
    "                        continue\n",
    "                    if (a, b) in visited:\n",
    "                        continue\n",
    "                    \n",
    "                    queue.append((a, b))\n",
    "                    visited.add((a, b))\n",
    "                    # grid[a][b] = 2\n",
    "                    # area += 1\n",
    "            \n",
    "            return area\n",
    "\n",
    "        \n",
    "        max_area = 0\n",
    "        for i in range(H):\n",
    "            for j in range(W):\n",
    "                if grid[i][j] == 1:\n",
    "                    area = get_area(i, j)\n",
    "                    max_area = max(area, max_area)\n",
    "        \n",
    "        return max_area"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:\n",
    "        ans = 0\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        directions = ((1, 0), (0, 1), (-1, 0), (0, -1))\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 1:\n",
    "                    area = 1\n",
    "                    grid[i][j] = 0\n",
    "                    queue = deque([[i, j]])\n",
    "                    while queue:\n",
    "                        [ti, tj] = queue.popleft()\n",
    "                        for (r, c) in directions:\n",
    "                            if 0 <= (ti + r) < m and 0 <= (tj + c) < n and grid[ti+r][tj+c] == 1:\n",
    "                                grid[ti+r][tj+c] = 0\n",
    "                                queue.append([ti+r, tj+c])\n",
    "                                area += 1\n",
    "                    ans = max(ans, area)\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        \n",
    "        def bfs(x, y):\n",
    "            grid[x][y] = 0\n",
    "            \n",
    "            q = []\n",
    "            q.append([x, y])\n",
    "            area = 1\n",
    "\n",
    "            directions = [[-1,0],[1,0],[0,-1],[0,1]]\n",
    "            while len(q) != 0:\n",
    "                # [new_x, new_y] = q.pop(0)\n",
    "                element = q.pop(0)\n",
    "                for direction in directions:\n",
    "                    # new_x += direction[0]\n",
    "                    # new_y += direction[1]\n",
    "                    new_x = element[0] + direction[0]\n",
    "                    new_y = element[1] + direction[1]\n",
    "                    if 0<=new_x<m and 0<=new_y<n and grid[new_x][new_y] == 1:\n",
    "                        grid[new_x][new_y] = 0\n",
    "                        q.append([new_x, new_y])\n",
    "                        area += 1\n",
    "            return area\n",
    "        \n",
    "        ans = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 1:\n",
    "                    area = bfs(i, j)\n",
    "                    if area > ans:\n",
    "                        ans = area\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # def DFS(self,grid: List[List[int]],checklist, i:int, j:int):\n",
    "        \n",
    "    #     checklist[i][j] = 1\n",
    "    #     self.area += 1\n",
    "    #     for nexti, nextj in [(i,j+1), (i,j-1), (i+1,j),(i-1,j)]:\n",
    "    #         if ((0 <= nexti < self.x and 0 <= nextj < self.y) and (grid[nexti][nextj] == 1) and checklist[nexti][nextj] == 0):\n",
    "    #             self.DFS(grid, checklist, nexti, nextj)\n",
    "\n",
    "    # def maxAreaOfIsland(self, grid: List[List[int]]) -> int:\n",
    "    #     #m为x，n为y\n",
    "    #     self.x = len(grid)\n",
    "    #     self.y = len(grid[0])\n",
    "    #     ans = 0\n",
    "    #     checklist = [[0] * self.y for _ in range(self.x)]\n",
    "\n",
    "    #     for i in range(self.x):\n",
    "    #         for j in range(self.y):\n",
    "    #             if (grid[i][j] == 1 and checklist[i][j] == 0):\n",
    "    #                 self.area = 0\n",
    "    #                 self.DFS(grid, checklist, i, j)\n",
    "    #                 ans = max(ans, self.area)\n",
    "\n",
    "    #     return ans\n",
    "\n",
    "    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:\n",
    "        x_len, y_len = len(grid), len(grid[0])\n",
    "        ans = 0\n",
    "        \n",
    "        checklist = [[0] * y_len for _ in range(x_len)]\n",
    "\n",
    "        for i in range(x_len):\n",
    "            for j in range(y_len):\n",
    "                if grid[i][j] == 1 and checklist[i][j] == 0:\n",
    "                    q = deque([(i,j)])\n",
    "                    checklist[i][j] = 1\n",
    "                    curarea = 0\n",
    "                    while len(q) > 0:\n",
    "                        x,y = q.popleft()\n",
    "                        curarea += 1\n",
    "                        for xnext, ynext in [(x,y+1),(x,y-1),(x+1,y),(x-1,y)]:\n",
    "                            if ((0 <= xnext < x_len and 0 <= ynext < y_len) and grid[xnext][ynext] == 1 and checklist[xnext][ynext] == 0):\n",
    "                                q.append((xnext,ynext))\n",
    "                                checklist[xnext][ynext] = 1\n",
    "                    ans = max(ans, curarea)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:\n",
    "        def island(grid,a,b,sur_max):\n",
    "            isl = []\n",
    "            isl.append((a,b))\n",
    "            grid[a][b] =0\n",
    "            sur = 1\n",
    "            while isl:\n",
    "                (i,j) = isl.pop()\n",
    "                for (p,q) in [(i-1,j),(i+1,j),(i,j-1),(i,j+1)]:\n",
    "                    if 0<=p<m and 0<=q<n and grid[p][q] ==1:\n",
    "                        grid[p][q] = 0\n",
    "                        isl.append((p,q))\n",
    "                        sur +=1\n",
    "            return max(sur_max,sur)\n",
    "\n",
    "        sur_max = 0\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] ==1:\n",
    "                    sur_max = island(grid,i,j,sur_max)\n",
    "        return sur_max\n",
    "        \n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:\n",
    "        if len(grid)==0 or len(grid[0]) == 0:\n",
    "            return 0\n",
    "\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        count = 0\n",
    "        visited = [[0 for _ in range(n)] for _ in range(m)]\n",
    "\n",
    "        def dfs(i, j, c, area):\n",
    "            for x, y in [(i+1,j), (i-1,j), (i,j+1), (i,j-1)]:\n",
    "                if x >= m or x < 0 or y >= n or y < 0:\n",
    "                    continue\n",
    "                if grid[x][y] == 0 or visited[x][y] != 0:\n",
    "                    continue\n",
    "                visited[x][y] = c\n",
    "                area+=1\n",
    "                area = dfs(x,y,c,area)\n",
    "\n",
    "            return area\n",
    "        \n",
    "        def bfs(i, j, c, area):\n",
    "            que = deque([(i,j)])\n",
    "            while que:\n",
    "                i, j = que.popleft()\n",
    "\n",
    "                for x, y in [(i+1,j), (i-1,j), (i,j+1), (i,j-1)]:\n",
    "                    if x >= m or x < 0 or y >= n or y < 0:\n",
    "                        continue\n",
    "                    if grid[x][y] == 0 or visited[x][y] != 0:\n",
    "                        continue\n",
    "                    visited[x][y] = c\n",
    "                    area+=1\n",
    "                    que.append((x,y))\n",
    "                    # area = dfs(x,y,c,area)\n",
    "\n",
    "            return area\n",
    "        \n",
    "        res = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 1 and visited[i][j] == 0:\n",
    "                    count += 1\n",
    "                    visited[i][j] = count\n",
    "                    area = bfs(i, j, count, 1)\n",
    "                    res = max(res, area)\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:\n",
    "        direction = [[-1,0],[1,0],[0,1],[0,-1]]\n",
    "        # def dfs(x,y):\n",
    "        #     if x < 0 or y < 0 or x >= len(grid) or y >= len(grid[0]):\n",
    "        #         return 0\n",
    "        #     if grid[x][y] == 0:\n",
    "        #         return 0\n",
    "        #     area = 1\n",
    "        #     grid[x][y] = 0\n",
    "        #     for p in direction:\n",
    "        #         area += dfs(x-p[0], y-p[1])\n",
    "        #     return area\n",
    "            \n",
    "        # max_area = 0\n",
    "        # for i in range(len(grid)):\n",
    "        #     for j in range(len(grid[0])):\n",
    "        #         if grid[i][j] == 0:\n",
    "        #             continue\n",
    "        #         max_area = max(max_area, dfs(i,j))\n",
    "        # return max_area\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "        max_area = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 0:\n",
    "                    continue\n",
    "                queue = []\n",
    "                queue.append([i,j])\n",
    "                area = 0\n",
    "                while queue != []:\n",
    "                    point = queue[-1]\n",
    "                    queue = queue[:-1]\n",
    "                    x,y = point\n",
    "                    if x < 0 or y < 0 or x >= m or y >= n:\n",
    "                        continue\n",
    "                    if grid[x][y] == 0:\n",
    "                        continue\n",
    "                    area += 1\n",
    "                    grid[x][y] = 0\n",
    "                    for dx, dy in direction:\n",
    "                        queue.append([x+dx, y+dy])\n",
    "                max_area = max(area, max_area)\n",
    "        return max_area\n",
    "                    \n",
    "                    \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        u = list(range(m * n))\n",
    "        def find(i):\n",
    "            if u[i] != i:\n",
    "                u[i] = find(u[i])\n",
    "            return u[i]\n",
    "        area = [0] * (m * n)\n",
    "        mx = 0\n",
    "        for r, row in enumerate(grid):\n",
    "            for c, val in enumerate(row):\n",
    "                i = r * n + c \n",
    "                if val:\n",
    "                    u[i] = i\n",
    "                    area[i] = 1\n",
    "                    if r > 0 and grid[r - 1][c]:\n",
    "                        b = find(i - n)\n",
    "                        if b != u[i]:\n",
    "                            area[b] += area[u[i]]\n",
    "                            u[i] = b\n",
    "                    if c > 0 and grid[r][c - 1]:\n",
    "                        b = find(i - 1)\n",
    "                        if b != u[i]:\n",
    "                            area[b] += area[u[i]]\n",
    "                            u[find(i)] = b\n",
    "                    if area[u[find(i)]] > mx:\n",
    "                        mx = area[u[find(i)]]\n",
    "        return mx"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:\n",
    "        m,n=len(grid),len(grid[0])\n",
    "\n",
    "\n",
    "        parent=list(range(m*n))\n",
    "\n",
    "        def find(i):\n",
    "            if i==parent[i]:return i\n",
    "            parent[i]=find(parent[i])\n",
    "            return parent[i]\n",
    "\n",
    "\n",
    "        def union(i,j):\n",
    "            rooti,rootj=find(i),find(j)\n",
    "            parent[rooti]=rootj\n",
    "\n",
    "\n",
    "        ll=[[1,0],[0,1]]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j]==0:continue\n",
    "\n",
    "                for ii,jj in ll:\n",
    "                    newi,newj=i+ii,j+jj\n",
    "                    if 0<=newi<m and 0<=newj<n and grid[newi][newj]:\n",
    "                        union(i*n+j,newi*n+newj)\n",
    "        \n",
    "\n",
    "        \n",
    "\n",
    "        dicc=defaultdict(int)\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j]:\n",
    "                    dicc[find(i*n+j)]+=1\n",
    "\n",
    "\n",
    "\n",
    "        return max(dicc.values()) if dicc.values() else 0\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:\n",
    "        result = 0\n",
    "        row_num = len(grid)\n",
    "        col_num = len(grid[0])\n",
    "        adj_dict = {(i, j): set() for i in range(row_num) for j in range(col_num)}\n",
    "        neighbours = [(1, 0), (-1, 0), (0, 1), (0, -1)]\n",
    "        for i in range(row_num):\n",
    "            for j in range(col_num):\n",
    "                if grid[i][j] == 0:\n",
    "                    continue\n",
    "                for a, b in neighbours:\n",
    "                    row = i + a\n",
    "                    col = j + b\n",
    "                    if 0 <= row < row_num and 0 <= col < col_num:\n",
    "                        if grid[row][col] == 0:\n",
    "                            continue\n",
    "                        adj_dict[(i, j)].add((row, col))\n",
    "                        adj_dict[(row, col)].add((i, j))\n",
    "\n",
    "        d = [[0 for i in range(col_num)] for j in range(row_num)]\n",
    "        g = 0\n",
    "        def bfs(u):\n",
    "            nonlocal d\n",
    "            nonlocal g\n",
    "            q = [u]\n",
    "            row_u, col_u = u\n",
    "            d[row_u][col_u] = 1\n",
    "            g += 1\n",
    "            while q:\n",
    "                u = q.pop()\n",
    "                row_u, col_u = u\n",
    "                for v in adj_dict[u]:\n",
    "                    row_v, col_v = v\n",
    "                    if d[row_v][col_v] == 0:\n",
    "                        g += 1\n",
    "                        d[row_v][col_v] = g\n",
    "                        q.append(v)\n",
    "\n",
    "\n",
    "        for i in range(row_num):\n",
    "            for j in range(col_num):\n",
    "                g = 0\n",
    "                if grid[i][j] == 0 or d[i][j] != 0:\n",
    "                    continue\n",
    "                bfs((i, j))\n",
    "        result = max(max(row) for row in d)\n",
    "\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def maxAreaOfIsland(self, grid: list[list[int]]) -> int:\r\n",
    "        m = len(grid)\r\n",
    "        n = len(grid[0])\r\n",
    "\r\n",
    "        def searchOne(searching, done, result):\r\n",
    "            if not searching:\r\n",
    "                return result\r\n",
    "            nonlocal m, n, grid\r\n",
    "            new_searching = []\r\n",
    "            for [r, c] in searching:\r\n",
    "                grid[r][c] = 0\r\n",
    "                for  [a, b] in [[-1, 0], [0, -1], [0, 1], [1, 0]]:\r\n",
    "                    rr, cc = r + a, c + b\r\n",
    "                    if [rr, cc] in done:\r\n",
    "                        continue\r\n",
    "                    if 0 <= rr < m and 0 <= cc < n:\r\n",
    "                        if grid[rr][cc] == 1:\r\n",
    "                            grid[rr][cc] = 0\r\n",
    "                            result += 1\r\n",
    "                            new_searching.append([rr, cc])\r\n",
    "                        done.append([rr, cc])\r\n",
    "            return searchOne(new_searching, done, result)\r\n",
    "\r\n",
    "        best = 0\r\n",
    "        for r in range(m):\r\n",
    "            for c in range(n):\r\n",
    "                if grid[r][c] == 1:\r\n",
    "                    area = searchOne([[r, c]], [[r, c]], 1)\r\n",
    "                    best = max(best, area)\r\n",
    "        return best\r\n",
    "                \r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:\n",
    "        row = len(grid)\n",
    "        col = len(grid[0])\n",
    "        visited = [[False]*col for _ in range(row)]\n",
    "        max_count = 0\n",
    "        for i in range(row):\n",
    "            for j in range(col):\n",
    "                count = 0\n",
    "                cur_count = self.dfs(i,j,visited,grid,row,col,count)\n",
    "                if cur_count >max_count:\n",
    "                    max_count = cur_count\n",
    "        return max_count\n",
    "\n",
    "    def dfs(self,x,y,visited,grid,row,col,count):\n",
    "        directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]\n",
    "        if x< 0 or x>= row or y<0 or y>= col:\n",
    "            return count\n",
    "        if grid[x][y] != 1 or visited[x][y]:\n",
    "            return count\n",
    "        visited[x][y] = True\n",
    "        count +=1\n",
    "        for direction in directions:\n",
    "            count = self.dfs(x+direction[0],y+direction[1],visited,grid,row,col,count)\n",
    "        return count\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:\n",
    "\n",
    "        n_row, n_col = len(grid), len(grid[0])\n",
    "        max_area = 0\n",
    "\n",
    "        def _dfs(row, col):\n",
    "            if row < 0 or row >= n_row or col < 0 or col >= n_col:\n",
    "                return 0\n",
    "            elif grid[row][col] == 0: return 0\n",
    "            grid[row][col] = 0\n",
    "            up = _dfs(row - 1, col)\n",
    "            down = _dfs(row + 1, col)\n",
    "            left = _dfs(row, col - 1)\n",
    "            right = _dfs(row, col + 1)\n",
    "            return up + down + left + right + 1\n",
    "\n",
    "        for row in range(n_row):\n",
    "            for col in range(n_col):\n",
    "                if grid[row][col] == 0: continue\n",
    "                max_area = max(max_area, _dfs(row, col))\n",
    "        return max_area\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:\n",
    "\n",
    "        row, col = len(grid), len(grid[0])\n",
    "        ans = 0\n",
    "\n",
    "        def process(x, y):\n",
    "            if x<0 or x>=row or y<0 or y>=col: return 0\n",
    "            if grid[x][y] != 1: return 0\n",
    "\n",
    "            grid[x][y] = 2\n",
    "            return 1 + process(x+1, y) + process(x-1, y) + process(x, y+1) + process(x, y-1)\n",
    "\n",
    "            \n",
    "\n",
    "        for i in range(row):\n",
    "            for j in range(col):\n",
    "                if grid[i][j] == 1:\n",
    "                    temp = process(i,j)\n",
    "                    ans = max(ans, temp)\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        result = 0\n",
    "\n",
    "    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "        visited = [[0]*n for _ in range(m)]\n",
    "        maxresult =0\n",
    "        self.result = 0\n",
    "        dirs = [(0,-1),(-1,0),(0,1),(1,0)]\n",
    "\n",
    "        def dfs(x,y):\n",
    "            visited[x][y] = 1 \n",
    "            self.result +=1\n",
    "            for a, b  in dirs:\n",
    "                nextx = x+a\n",
    "                nexty = y+b\n",
    "                if nextx < 0 or nexty < 0 or nextx >=m or nexty >=n:\n",
    "                    continue\n",
    "                if visited[nextx][nexty] == 0  and grid[nextx][nexty] ==1:\n",
    "                    dfs(nextx,nexty)\n",
    "              \n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if visited[i][j] == 0 and grid[i][j] ==1:\n",
    "                     self.result = 0\n",
    "                     dfs(i,j)\n",
    "                     maxresult=max(maxresult,self.result)\n",
    "        return maxresult\n",
    "                \n",
    "        \n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:\n",
    "        res = 0\n",
    "        self.m = len(grid)\n",
    "        self.n = len(grid[0])\n",
    "\n",
    "        for i in range(self.m):\n",
    "            for j in range(self.n):\n",
    "                if grid[i][j] == 1:\n",
    "                    res = max(res, self.dfs(grid, i, j))\n",
    "\n",
    "        return res\n",
    "\n",
    "    def dfs(self, grid, i, j):\n",
    "        if i < 0 or i >= self.m or j < 0 or j >=self.n:\n",
    "            return 0\n",
    "\n",
    "        if grid[i][j] == 0:\n",
    "            return 0\n",
    "\n",
    "        grid[i][j] = 0\n",
    "        return self.dfs(grid, i-1, j) + self.dfs(grid, i+1, j) + self.dfs(grid, i, j-1) + self.dfs(grid, i, j+1) + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:\n",
    "        if len(grid) == 0:\n",
    "            return 0\n",
    "        \n",
    "        ans = 0\n",
    "        for i in range(len(grid)):\n",
    "            for j in range(len(grid[0])):\n",
    "                if grid[i][j] == 1:\n",
    "                    area = self.dfs(i, j, grid)\n",
    "                    ans = max(ans, area)\n",
    "        return ans\n",
    "\n",
    "    def dfs(self, i, j, grid):\n",
    "        if i < 0 or i == len(grid) or j < 0 or j == len(grid[0]) or grid[i][j] == 0:\n",
    "            return 0\n",
    "        \n",
    "        grid[i][j] = 0  # mark visited sites\n",
    "        return 1 + self.dfs(i+1, j, grid) +  self.dfs(i-1, j, grid) \\\n",
    "               + self.dfs(i, j+1, grid) + self.dfs(i, j-1, grid)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "\n",
    "        dp = [[False]*n for _ in range(m)]\n",
    "\n",
    "        def dfs(x,y,cnt):\n",
    "            # print(1)\n",
    "            # print(x,y)\n",
    "            # print(dp[x][y])\n",
    "            if dp[x][y]:\n",
    "                return cnt\n",
    "            cnt += 1\n",
    "            dp[x][y] = True\n",
    "\n",
    "            dire = ((x-1,y),(x,y+1),(x+1,y),(x,y-1))#上右下左\n",
    "            for nx, ny in dire:\n",
    "                # print(nx,ny)\n",
    "                if nx >= 0 and nx < m and ny >= 0 and ny < n:\n",
    "                    if grid[nx][ny] == 1:\n",
    "                        cnt = dfs(nx,ny,cnt)\n",
    "            return cnt\n",
    "\n",
    "        # cnt = 0\n",
    "        # cnt = dfs(0,7,cnt)\n",
    "        # print(cnt)\n",
    "            \n",
    "\n",
    "        cnt_list = []\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 0:\n",
    "                    continue\n",
    "                else:\n",
    "                    if not dp[i][j]:\n",
    "                        cnt = 0\n",
    "                        cnt = dfs(i,j,cnt)\n",
    "                        cnt_list.append(cnt)\n",
    "        if not cnt_list:\n",
    "            return 0\n",
    "        else:\n",
    "            return max(cnt_list)\n",
    "                        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        visited = [[False] * n for _ in range(m)]\n",
    "        \n",
    "        max_area = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if not visited[i][j] and grid[i][j] == 1:\n",
    "                    area = self.dfs(grid, visited, m, n, i, j)\n",
    "                    max_area = max(max_area, area)\n",
    "        return max_area\n",
    "                    \n",
    "    \n",
    "    def dfs(self, grid, visited, m, n, x, y):\n",
    "        visited[x][y] += 1\n",
    "        area = 1\n",
    "        \n",
    "        directions = [[0, -1], [0, 1], [1, 0], [-1, 0]]\n",
    "        for d in directions:\n",
    "            next_x, next_y = x + d[0], y + d[1]\n",
    "            if (0 <= next_x < m and \n",
    "                0 <= next_y < n and \n",
    "                grid[next_x][next_y] == 1 and\n",
    "                not visited[next_x][next_y]):\n",
    "                area += self.dfs(grid, visited, m, n, next_x, next_y)\n",
    "        return area\n",
    "                \n",
    "                \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.count = 0\n",
    "\n",
    "    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:\n",
    "        if not grid:\n",
    "            return 0\n",
    "        result = 0\n",
    "        m =len(grid)\n",
    "        n = len(grid[0])\n",
    "        visited= [[False]*n for _ in range(m)]\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 1 and not visited[i][j]:\n",
    "                    self.count = 0\n",
    "                    self.dfs(grid, visited, i, j)\n",
    "                    result = max(result, self.count)\n",
    "\n",
    "        return result\n",
    "\n",
    "\n",
    "\n",
    "    def dfs(self, grid, visited, x, y):\n",
    "        if grid[x][y] == 0 or visited[x][y]:\n",
    "            return \n",
    "        visited[x][y] = True\n",
    "        self.count += 1\n",
    "        for new_x,new_y in [(x+1, y), (x-1, y), (x, y-1), (x, y+1)]:\n",
    "            if 0 <= new_x < len(grid) and 0 <= new_y < len(grid[0]):\n",
    "                self.dfs(grid, visited, new_x, new_y)"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
